package main.Q901_1000;

import java.util.*;

public class Q981_990 {
    public static void main(String[] args) {
        System.out.println("Question981：基于时间的键值存储");
        System.out.println("Question982：");
        System.out.println("Question983：最低票价");
        System.out.println("Question984：不含 AAA 或 BBB 的字符串");
        System.out.println("Question985：查询后的偶数和");
        System.out.println("Question986：区间列表的交集");
        System.out.println("Question987：");
        System.out.println("Question988：");
        System.out.println("Question989：数组形式的整数加法");
        System.out.println("Question990：");
    }
}

class TimeMap {
    public Map<String, TreeMap<Integer, String>> map;

    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        TreeMap<Integer, String> tree = map.getOrDefault(key, new TreeMap<>());
        tree.put(timestamp, value);
        map.put(key, tree);
    }

    public String get(String key, int timestamp) {
        TreeMap<Integer, String> tree = map.getOrDefault(key, new TreeMap<>());

        Map.Entry<Integer, String> entry = tree.floorEntry(timestamp);
        return entry == null ? "" : entry.getValue();
    }
}

class Question983 {
    public int mincostTickets(int[] days, int[] costs) {
        if (days == null || days.length == 0 ||
                costs == null || costs.length == 0) {
            return 0;
        }
        int[] dp = new int[days[days.length - 1] + 1];
        dp[0] = 0;
        for (int day : days) {
            dp[day] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < dp.length; i++) {
            if (dp[i] == 0) {//不需要买票
                dp[i] = dp[i - 1];
                continue;
            }
            int n1 = dp[i - 1] + costs[0];//当天需要买票
            int n2 = i > 7 ? dp[i - 7] + costs[1] : costs[1];
            int n3 = i > 30 ? dp[i - 30] + costs[2] : costs[2];
            dp[i] = Math.min(n1, Math.min(n2, n3));
        }
        return dp[days[days.length - 1]];
    }
}

class Question984 {
    public String strWithout3a3b(int a, int b) {
        String result = "";
        while (a > 0 && b > 0) {
            if (a > b) {
                result += "aab";
                a -= 2;
                b--;
            } else if (a == b) {
                result += "ab";
                a--;
                b--;
            } else {
                result += "bba";
                b -= 2;
                a--;
            }
        }
        while (a > 0) {
            result += "a";
            a--;
        }
        while (b > 0) {
            result += "b";
            b--;
        }
        return result;
    }
}

class Question985 {
    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int[] result = new int[nums.length];
        int total = 0;
        for (int num : nums) {
            if (num % 2 == 0) total += num;
        }
        for (int i = 0; i < nums.length; i++) {
            int val = queries[i][0], index = queries[i][1];
            int temp = val + nums[index];
            if (val % 2 == 0 && nums[index] % 2 == 0) {//原本为偶数，增量也为偶数
                total += val;
                nums[index] = temp;
            } else if (nums[index] % 2 != 0 && val % 2 != 0) {//原本为奇数，增量也为奇数
                nums[index] = temp;
                total += temp;
            } else if (nums[index] % 2 == 0 && val % 2 != 0) {//原本为偶数，增量为奇数
                total -= nums[index];
                nums[index] = temp;
            } else {//原本为奇数，增量为偶数
                nums[index] = temp;
            }
            result[i] = total;
        }
        return result;
    }
}

class Question986 {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> list = new ArrayList<>();
        int i = 0, j = 0;
        int[] first, second;
        while (i < firstList.length && j < secondList.length) {
            first = firstList[i];//获取当前区间
            second = secondList[j];
            int start = -1, end = -1;//判断交集区间
            if (first[0] > second[1] || second[0] > first[1]) ;//无交集
            else {
                start = Math.max(first[0], second[0]);//起始取大
                end = Math.min(first[1], second[1]);//结尾取小
                list.add(new int[]{start, end});
            }
            if (first[1] > second[1]) j++;//first在后
            else if (first[1] < second[1]) i++;//second在后
            else if (first[1] == second[1]) {//结尾相同，均更换为下一个区间
                i++;
                j++;
            }
        }
        int[][] result = new int[list.size()][];
        for (int k = 0; k < list.size(); k++) {
            result[k] = list.get(k);
        }
        return result;
    }
}

class Question989 {
    public List<Integer> addToArrayForm(int[] num, int k) {//数组与字符串长度不一
        List<Integer> list = new ArrayList<>();
        char[] str = String.valueOf(k).toCharArray();
        int i = num.length - 1, j = str.length - 1, last = 0;
        while (i >= 0 && j >= 0) {
            int temp = str[j] - '0';
            int total = num[i] + temp + last;
            last = total / 10;
            list.add(0, total % 10);
            i--;
            j--;
        }
        while (i >= 0) {
            if (last != 0) {
                int temp = num[i] + last;
                last = temp / 10;
                list.add(0, temp % 10);
            } else list.add(0, num[i]);
            i--;
        }
        ;
        while (j >= 0) {
            if (last != 0) {
                int temp = str[j] - '0' + last;
                last = temp / 10;
                list.add(0, temp % 10);
            } else list.add(0, str[j] - '0');
            j--;
        }
        if (last != 0) {
            list.add(0, last);
        }
        return list;
    }
}